1. Field Of Invention
The present invention relates generally a method and apparatus for converting field-programmable logic cell implementations into mask-programmable logic cell implementations. More particularly, the present invention relates to an improved method and apparatus for converting field-programmable gate array (FPGA) implementations into mask-programmable gate array (MPGA) implementations or into mask-programmable standard cell (MPSC) implementations.
2. Brief Description Of The Prior Art
Electronic devices, such as integrated circuit (IC) chips, are presently used in diverse fields of human endeavor, including, for example, manufacturing, industry, science, defense, recreation, and education. Practically speaking, the purpose of such devices is to perform various functions upon the signals provided to the terminals (i.e., pins) thereof.
From a design standpoint, each device is characterized by the functions it performs, namely: relating (i.e., "mapping") its input signals to its output signals. In the case of digital electronic type devices, the input and output signals are constrained to discrete (i.e., binary) values or variables, and the number of mappings (i.e., functions) that can be performed between the digital input and output signals of the device is limited by the number of possible states that the device may attain and the state transitions that the device may undergo. The various mappings performed between the digital input and output variables of devices are universally described using Boolean algebra, and often these mappings are referred to as Boolean functions. The manner in which these Boolean functions are physically implemented or realized for any particular "digital electronic design" necessarily involves the use of simpler components (such as logic gates) which are capable of performing basic Boolean functions. The resulting logic circuits are typically simplified using conventional algebraic simplification methods, Karnaugh maps, truth tables and the like. Thus, by combining and interconnecting the inputs and outputs of a number of such logic gates in a particular manner, any particular digital logic design can be physically realized.
In general, the underlying technology that is to used to implement a particular digital logic design determines the types of logic gates that will be available for combination and interconnection to realize the input-output functions of the digital logic design. Thus in theory, there are an infinite number of ways in which to implement a particular digital logic design characterized by a specified set of Boolean expressions. The object in most cases, of course, is to find an implementation that realizes the functions of the design using a minimal number of logic gates.
Upon completion of a specific digital logic design, it is necessary to physically implement the digital logic design using an available technology. In recent times, field-programmable gate array (FPGA) devices have enjoyed great popularity in low-risk prototyping and low-volume production applications.
Structurally, each field-programmable gate array device comprises a number of basic components realized on a silicon substrate that is contained in a chip package, namely: the pins on the chip package; an array of configurable logic blocks (CLB) for performing basic logic operations; a set of input/output interface blocks (IOB) for interfacing the pins on the chip package with particular CLBs; and programmable interconnect switching gates for performing signal routing functions among the CLBs and the IOBs.
Typically, each CLB and IOB has combinational and sequential logic which can be selectively configured to realize a desired logic function defined between the inputs and outputs thereof. Each CLB and IOB also has associated random access memory (RAM) for storing a configuration program that serves to select particular logic functions to be implemented. Similarly, each switching gate also has associated random access memory for storing digital code that serves to effect signal routing among the input and output ports of the CLBs and IOBs. The function of the interconnect switching gates are to facilitate controlled routing of signals among the CLBs and IOBs, as determined by the digital code stored in the random access memory of these switching gates. In order to physically implement (i.e., realize) a particular digital logic design using a FPGA device, all that is required is programming a suitable digital code into the RAM of each utilized CLB, IOB, and switching gate on the silicon substrate of the FPGA device.
It will be helpful to describe in greater detail below how a digital logic design is implemented using a conventional FPGA device.
As illustrated in Block A of FIG. 1A, the first step in the FPGA implementation method involves generating a digital logic design using, for example, logic synthesis or schematic capture techniques well known in the art. This step provides a set of Boolean logic expressions which fully represent the digital logic design.
As indicated at Block B in FIG. 1A, the second step in the method involves using a computer to produce a hardware description of the FPGA implementation. This subprocess requires using a high-level hardware description language that can be interpreted by the computer running the development program. For the Xilinx 2000 and 3000 Series FPGA devices, the FPGA implementation is described using a language specified by the Xilinx Netlist File Format (XNF). Taken together, the set of descriptive statements which describe the components in the FPGA implementation, is referred to as an original "netlist". Notably, each CLB and IOB description in the original netlist does not have a Logic Model Description, which specifies the logic within each CLB (i.e., subnetwork) and IOB. The syntax of the XNF hardware description language and the Logic Cell Array (LCA) library are described in great detail in the LCA Xilinx Netlist Specification, Version 2.00-Jan. 26, 1989, (69 pages) by Xilinx, Inc. of San Jose, Calif., which is incorporated herein by reference in its entirety.
As indicated at Block C in FIG. 1A, the third step of the method involves using the original XNF netlist and the "xnfmap" program from Xilinx in order to map groups of logic in the digital logic design, to CLBs in the FPGA device. This step produces a Logic Cell Array (LCA) description for each CLB and each IOB. The "map21ca" program from Xilinx is then used to produce an LCA description which may include up to 64 CLB descriptions, 60 IOB descriptions, a signal pin-out description, and a clock driver description.
As indicated at Block D in FIG. 1A, the fourth step in the method involves using the "lca2xnf" program from Xilinx in order to translate the LCA description into a final FPGA netlist which contains CLB and IOB placement specifications, and signal routing information for the FPGA implementation. The set of XNF statements that realize a CLB description in an exemplary FPGA netlist is shown in FIG. 2.
Thereafter, as indicated at Block E in FIG. 1B, computer system 2 executes the "makebits" program from Xilinx using the final FPGA XNF netlist in order to generate "configuration programs" (i.e., digital code) for the random access memories of the CLB, IOB and signal routing components aboard the FPGA device. In essence, the functions of the CLBs, IOBs and interconnect switches are controlled by these programs. These programs are stored in external memory. Upon power up or command, these digital codes are loaded into respective RAM elements, as indicated at Block G, to complete the programming of the FPGA device and thus physically realize the digital logic design.
Notably, the FPGA has both advantages and disadvantages. For example, after testing a programmed FPGA device using test vectors, it is easy and inexpensive to modify the original digital logic design and then reprogram the device accordingly. However, typical FPGA implementations have a high piece-part cost, and while suitable for prototyping and low-volume production, are often too expensive for high volume production. Consequently, when the demand for a particular digital logic design exceeds a certain threshold, economic considerations dictate that a different, more economically feasible technology be used to implement the successful digital logic design.
The process of implementing the functionality of a FPGA implementation in another digital technology, such as a mask-programmable gate array (MPGA) device is commonly referred to as "migration" or "implementation conversion" and has received much attention in recent times. In general, the conversion process requires mapping logic elements (such as flip-flops) and input/output (I/O) pads in the FPGA device, to their equivalent structures in the MPGA device and then resynthesizing the logic elements using logic elements available in the MPGA Library. However, when it is time to carry out the conversion process, it is often the case that the original designers of the FPGA implementation are not available to assist in the conversion (i.e., migration) of the FPGA implementation to another technology, such as mask-programmable gate array (MPGA) or mask-programmable standard cell (MPSC) technology.
In response to the need for FPGA to MPGA implementation conversions, a number of semi-automated conversion processes have been developed and are presently being used in commercial practice. In FIG. 3, a prior art method is shown for converting from an FPGA implementation into a MPGA implementation. As indicated at Block A, the first step of this method involves converting the XNF description of the FPGA implementation (produced by the process of FIG. 1), into a "flat" XNF description of the FPGA implementation. The object of this step is to remove all network level constraints on the FPGA implementation, which are imposed by the CLB boxes in the FPGA netlist. In the resulting "flat" netlist description, only gate-level logic specifications are presented. With this flat description, the logic gates, which were once confined within a CLB in the FPGA implementation, are now free to be regrouped with other logic gates and subsequently relocated on the MPGA substrate. The actual regrouping and relocation of these logic gates will be determined in accordance with the implementation scheme determined by the target technology being used in the conversion.
As indicated at Block B of FIG. 3, the second step of the method involves converting the flat FPGA netlist into the desired MPGA netlist for subsequent implementation. Then as indicated at Block C, the method involves using the MPGA netlist and the MPGA Library in order to generate a MPGA geometrical database. Notably, this geometrical database contains place and route information necessary to produce a number of "processing masks" needed to form a composite metalization pattern upon the MPGA substrate. Notably, the composite metalization pattern ultimately programs the device and realizes a MPGA implementation that is functionally equivalent to the FPGA implementation and the original digital logic design. Then at Block D, the MPGA geometrical database is used to produce the processing masks. The final step, indicated at Block E, involves using the produced processing masks to physically deposit the metalization pattern at the interconnect level of the MPGA substrate and thus realize the MPGA implementation.
While the above described method of converting from an FPGA implementation to a MPGA implementation has proved useful, it has suffered from a number of serious problems which have been described in detail in following articles: "FPGA Conversion" by Charles H. Small, in Electronic Design News, Jun. 4, 1992, pages 107-116; "FPGA-to-ASIC move takes planning" by Richard Goering, in Electronic Engineering Times, Apr. 27, 1992, Pages 45 and 46; and "AT&T AIC Application Note: Softpath Migrations: Field Programmable Gate Array to Gate Array or Standard Cell", August, 1992.
The most general statement of these problems is provided in the article "FPGA Conversion", supra. The first problem relates to the fact that each combinational logic block in the FPGA device has associated with it an inherent time delay, which is substantially constant and independent of the particular function being emulated thereby. The second problem relates to the fact that the programmable interconnect points and switching gates, required to perform signal routing operations in the FPGA device, introduce substantial signal delays which oftentimes can change or alter the logic functions being implemented within the device.
When implementing desired logic functions in a FPGA device, the above problems are easily handled by modeling these signal delays in the FPGA implementation (i.e., by the introduction of time delay blocks in the FPGA netlist). Notably, these time delays are explicitly represented in the statements used to realize various components described in the netlist.
However, when performing FPGA to MPGA implementation conversions using prior art methodologies, there typically is an unpredictable spatial mapping of CLB logic from the FPGA substrate onto the MPGA substrate, as illustrated in schematic representation of FIG. 4. Consequently, it has not been possible to solve the time delay problems described above and, in fact, other timing problems are oftentimes created during the technology conversion process.
Thus, there is a great need in the art to provide a method and apparatus for converting a FPGA implementation into a mask-programmable logic cell implementation, such as a MPGA implementation or MPSC implementation, while overcoming the problems associated with prior art systems and processes.